home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / GenericKeyedHeap.cc,v < prev    next >
Text File  |  1988-10-12  |  6KB  |  299 lines
  1. head     1.1;
  2. access   ;
  3. symbols  ;
  4. locks    grunwald:1.1; strict;
  5. comment  @@;
  6.  
  7.  
  8. 1.1
  9. date     88.09.18.16.42.22;  author grunwald;  state Exp;
  10. branches ;
  11. next     ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18.  
  19. 1.1
  20. log
  21. @Initial revision
  22. @
  23. text
  24. @#include "Awesime.h"
  25. #include "stream.h"
  26. //
  27. //    This defines a Pairing Heap structure for a pointer data type.
  28. //
  29. //    See ``The Pairing Heap: A New Form of Self-Adjusting Heap''
  30. //    Fredman, Segdewick et al,
  31. //    Algorithmica (1986) 1:111-129
  32. //
  33. //    In particular, this implements the pairing heap using the circular
  34. //    list.
  35. //
  36. //
  37.  
  38. const GENERIC2(HEAP_NAME,Index)  GENERIC2(HEAP_NAME,Null) = HEAP_INDEX_NULL;
  39.  
  40. #define NIL    GENERIC2(HEAP_NAME,Null)
  41. #define INDEX    GENERIC2(HEAP_NAME,Index)
  42. #define KEY    GENERIC2(HEAP_NAME,Key)
  43. #define ITEM    GENERIC2(HEAP_NAME,Item)
  44.  
  45. static const char *GENERIC2(HEAP_NAME,Name) = GENERIC_STRING(HEAP_NAME) ;
  46.  
  47. HEAP_NAME::HEAP_NAME(int length, bool xdebug)
  48.     : (xdebug)
  49. {
  50.     freelist = NIL;
  51.     allocatedSize = 0;
  52.     root = NIL;
  53.     elements = 0;
  54.     makeRoom(length);
  55. }
  56.  
  57. void
  58. HEAP_NAME::makeRoom(int atLeast)
  59. {
  60.     //
  61.     //    Out of free space?
  62.     //
  63.     if (freelist == NIL) {
  64.     //
  65.     // Is there existing storage?
  66.     //
  67.     if (allocatedSize > 0) {
  68. #ifdef _CPPTWO_
  69. #pragma linkage C
  70. #endif /*_CPPTWO_*/
  71.         extern bcopy(void *, void *, int);
  72. #ifdef _CPPTWO_
  73. #pragma linkage
  74. #endif /*_CPPTWO_*/
  75.         
  76.         //
  77.         // Get new storage, copy over existing data & delete old storage
  78.         // 
  79.         INDEX newSize = (allocatedSize * 3) / 2;
  80.  
  81.         GENERIC2(HEAP_NAME,Record) *newStorage = new GENERIC2(HEAP_NAME,Record)[newSize];
  82.         char *newValid = new char[newSize];
  83.         if (newStorage == 0 || newValid == 0) {
  84.         cerr << "[" << GENERIC2(HEAP_NAME,Name) << "::makeRoom] Out of storage space\n";
  85.         exit(1);
  86.         }
  87.         bcopy(storage, newStorage, allocatedSize * sizeof(GENERIC2(HEAP_NAME,Record)));
  88.         bcopy(pValid, newValid, allocatedSize * sizeof(char));
  89.         delete storage;
  90.         delete pValid;
  91.         storage = newStorage;
  92.         pValid = newValid;
  93.         //
  94.         // Chain the new stuff into the free list
  95.         //
  96.         for (int i = allocatedSize; i < newSize; i++) {
  97.         storage[i].sibling = i+1;
  98.         pValid[i] = 0;
  99.         }
  100.         storage[newSize-1].sibling = NIL;
  101.         freelist = allocatedSize;
  102.         allocatedSize = newSize;
  103.     } else {
  104.         //
  105.         // No existing space
  106.         //
  107.         if (atLeast <= 8) {
  108.         allocatedSize = 8;
  109.         } else {
  110.         allocatedSize = atLeast;
  111.         }
  112.         storage = new GENERIC2(HEAP_NAME,Record)[allocatedSize];
  113.         pValid = new char[allocatedSize];
  114.         if (storage == 0) {
  115.         cerr << "[" << GENERIC2(HEAP_NAME,Name) << "::getCell] Out of storage\n";
  116.         exit(1);
  117.         }
  118.         for (int i = 0; i < allocatedSize; i++) {
  119.         storage[i].sibling = i+1;
  120.         pValid[i] = 0;
  121.         }
  122.         storage[allocatedSize-1].sibling = NIL;
  123.         freelist = 0;
  124.     }
  125.     }
  126. }
  127.  
  128. //
  129. // makeChild takes two nodes and makes one the child of the other
  130. // and returns the index of the new parent. 
  131. //
  132. // We play fast and loose with the siblings field of a & b, although
  133. // we maintain the siblings of the children.
  134. //
  135. INDEX
  136. HEAP_NAME::makeChild(INDEX a, INDEX b)
  137. {
  138.     INDEX parent;
  139.     INDEX child;
  140.     
  141.     if (storage[a].key <= storage[b].key) {
  142.     parent = a; child = b;
  143.     } else {
  144.     parent = b; child = a;
  145.     }
  146.     //
  147.     // If the new parent has no children, simply add the new child.
  148.     // We assume that the child and the parent dont care about
  149.     // their *sibling* nodes
  150.     //
  151.     INDEX popsKid = storage[parent].children;
  152.     
  153.     if (popsKid == NIL) {
  154.     storage[parent].children = child;
  155.     storage[child].sibling = child;
  156.     } else {
  157.     INDEX temp = storage[popsKid].sibling;
  158.     storage[popsKid].sibling = child;
  159.     storage[child].sibling = temp;
  160.     storage[parent].children = child;
  161.     }
  162.     return(parent);
  163. }
  164.  
  165. void
  166. HEAP_NAME::add(KEY *key, ITEM *item)
  167. {
  168.     INDEX cell = getCell();
  169.  
  170.     storage[cell].key = *key;
  171.     storage[cell].item = *item;
  172.     storage[cell].children = NIL;
  173.     storage[cell].sibling = NIL;
  174.     
  175.     if (root == NIL) {
  176.     root = cell;
  177.     } else {
  178.      //
  179.     //    Make cell a child of root. Root may have no kids.
  180.     //
  181.     root = makeChild(root,cell);
  182.     }
  183. }
  184.  
  185. //
  186. //    Item remove is the most complicated routine.
  187. //
  188. //    We remove the root (should there be one) and then select a new
  189. //    root. The siblings of the root are in a cicular list. We continue
  190. //    to pair elements in this list until there is a single element.
  191. //    This element will be the new root.
  192. bool
  193. HEAP_NAME::remove(KEY *key, ITEM *removed)
  194. {
  195.     bool valid = FALSE;
  196.     
  197.     do {
  198.     if (root == NIL || elements <= 0) {
  199.         return(0);
  200.     }
  201.     
  202.     *key = storage[root].key;
  203.     *removed = storage[root].item;
  204.     valid = pValid[root];
  205.     
  206.     INDEX child = storage[root].children;
  207.     returnCell(root);
  208.     
  209.     if (child == NIL) {
  210.         root = NIL;
  211.     } else {
  212.         while(storage[child].sibling != child) {
  213.         //
  214.         // We have at least two kids, but we may only have
  215.         // two kids. So, oneChild != child, but it is possible
  216.         // that twoChild == child.
  217.         //
  218.         INDEX oneChild = storage[child].sibling;
  219.         INDEX twoChild = storage[oneChild].sibling;
  220.         //
  221.         // Remove the two from the sibling list
  222.         //
  223.         storage[child].sibling = storage[twoChild].sibling;
  224.         storage[oneChild].sibling = NIL;
  225.         storage[twoChild].sibling = NIL;
  226.         
  227.         INDEX bestChild = makeChild(oneChild, twoChild);
  228.         
  229.         if (twoChild == child) {
  230.             //
  231.             // We have reduced the two to one, so we'll be exiting.
  232.             //
  233.             child = bestChild;
  234.             storage[child].sibling = child;
  235.         } else {
  236.             //
  237.             // We've removed two siblings, now we need to insert
  238.             // the better of the two
  239.             //
  240.             storage[bestChild].sibling = storage[child].sibling;
  241.             storage[child].sibling = bestChild;
  242.             child = storage[bestChild].sibling;
  243.         }
  244.         }
  245.         root = child;
  246.     }
  247.     } while ( !valid );
  248.     return(1);
  249. }
  250.  
  251. bool
  252. HEAP_NAME::doStart(INDEX &index)
  253. {
  254.     for (index = 0; index < allocatedSize; index++) {
  255.     if (pValid[index]) {
  256.         return(TRUE);
  257.     }
  258.     }
  259.     return(FALSE);
  260. }
  261.  
  262. bool
  263. HEAP_NAME::doDelete(INDEX &index)
  264. {
  265.     if (pValid[index]) {
  266.     pValid[index] = FALSE;
  267.     elements--;
  268.     return(TRUE);
  269.     } else {
  270.     return( FALSE );
  271.     }
  272. }
  273.  
  274. bool
  275. HEAP_NAME::doNext(INDEX& index)
  276. {
  277.     //
  278.     // If they are moving on to the next element,
  279.     // they are sitting on the current on. So, move to the next
  280.     // and then look for a valid one.
  281.     //
  282.     for (index++; index < allocatedSize; index++) {
  283.     if (pValid[index]) {
  284.         return(TRUE);
  285.     }
  286.     }
  287.     return(FALSE);
  288. }
  289.  
  290. void
  291. HEAP_NAME::doDone()
  292. {
  293.     //
  294.     // Do nothing.
  295.     //
  296. }
  297.  
  298. @
  299.